package com.leetcode.www;

import java.util.ArrayList;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-queens
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-17
 * Time:17:30
 */
class pair{
    public int x;
    public int y;
    public pair(int x,int y){//用来存放每个位置坐标
        this.x = x;
        this.y = y;
    }
}
public class DFS51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<pair>> newRet = new ArrayList<>();
        List<pair> newList = new ArrayList<>();
        DFS(newRet,newList,0,n);
        return trans(newRet,n);
    }
    //转换位置矩阵为目标矩阵
    public List<List<String>> trans(List<List<pair>> newRet,int n){
        List<List<String>> ret = new ArrayList<>();

        for(List<pair> l : newRet){
            //l代表每一个不同的解法
            List<StringBuilder> cur = new ArrayList<>();//过程矩阵,后面通过这个来转化为目标矩阵
            for(int i = 0;i < n;i ++){
                StringBuilder sb = new StringBuilder();
                for(int j = 0;j < n;j ++){
                    sb.append(".");//先将所有位置放上 .
                }
                cur.add(sb);
            }

            for(pair p : l){
                cur.get(p.x).setCharAt(p.y,'Q');//修改每个皇后的位置为Q
            }
            List<String> list = new ArrayList<>();
            for(StringBuilder s : cur){//再将转换好的list放到答案解集中去
                list.add(s.toString());
            }

            ret.add(list);//最后再放入目标矩阵集合中去
        }
        return ret;
    }
    //深度优先搜索
    public void DFS(List<List<pair>> newRet, List<pair> newList, int newRow, int n){
        //临界条件
        if(newRow == n){
            newRet.add(new ArrayList<>(newList));
            return;
        }
        for(int i = 0;i < n;i ++){
            if(isTrue(newList,newRow,i)){
                newList.add(new pair(newRow,i));//当前行的的这个坐标可以放
                DFS(newRet,newList,newRow + 1,n);
                newList.remove(newList.size() - 1);//回溯
            }
        }
    }
    //判断哪一个位置可以存放
    public boolean isTrue(List<pair> newList,int newRow,int newCol){
        for(pair p : newList){
            //判断每一行是否存在同列和同斜线的位置
            if(p.y == newCol || (Math.abs(p.x - newRow) == Math.abs(p.y - newCol))){
                return false;
            }
        }
        return true;
    }
}
